//链式队列
#ifndef __LINKEDQUEUE__HPP
#define __LINKEDQUEUE__HPP

#include"VirtualQueue.hpp"

namespace NgSiuKei {

template<class TheClass>
struct linked_queue_node {
    TheClass val;
    linked_queue_node<TheClass> *next;
    linked_queue_node<TheClass> *prev;
};
#define lq_node linked_queue_node

template<class TheClass>
class LinkedQueue: public VirtualQueue<TheClass> {
    public:
    LinkedQueue(void);
    ~LinkedQueue(void);

    public:
    //清空
    void clear(void);
    //获取队头元素
    TheClass getFrontVal(void) const;
    //入队列
    virtual void push(const TheClass val);
    //出队列
    TheClass pop(void);
    //打印队列
    virtual void print(void) const;

    protected:
    lq_node<TheClass> *front;
    lq_node<TheClass> *rear;
};

template<class TheClass>
LinkedQueue<TheClass>::LinkedQueue(void) {
    this->front = nullptr;
    this->rear = nullptr;
}

template<class TheClass>
LinkedQueue<TheClass>::~LinkedQueue(void) {
    this->clear();
}

template<class TheClass>
void LinkedQueue<TheClass>::clear(void) {
    if(nullptr == this->front && nullptr == this->rear) {
        return;
    }
    this->size = 0;
    lq_node<TheClass> *currentNode = this->front;
    lq_node<TheClass> *deleteNode = nullptr;
    while(nullptr != currentNode) {
        deleteNode = currentNode;
        currentNode = currentNode->next;
        delete deleteNode;
    }
    this->front = nullptr;
    this->rear = nullptr;
}

template<class TheClass>
TheClass LinkedQueue<TheClass>::getFrontVal(void) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    return this->front->val;
}

template<class TheClass>
void LinkedQueue<TheClass>::push(const TheClass val) {
    lq_node<TheClass> *newNode = new lq_node<TheClass>;
    newNode->val = val;
    if(this->isEmpty()) {
        this->front = newNode;
        this->rear = newNode;
        this->front->prev = nullptr;
        this->front->next = nullptr;
        this->rear->prev = nullptr;
        this->rear->next = nullptr;
    }
    else {
        this->rear->next = newNode;
        newNode->prev = this->rear;
        newNode->next = nullptr;
        this->rear = newNode;
    }
    this->size++;
}

template<class TheClass>
TheClass LinkedQueue<TheClass>::pop(void) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }

    this->size--;
    TheClass resultVal = this->front->val;
    lq_node<TheClass> *deleteNode = this->front;
    if(0 == this->size) {
        this->front = nullptr;
        this->rear = nullptr;
    }
    else {
        this->front = this->front->next;
        this->front->prev = nullptr;
    }
    delete deleteNode;
    return resultVal;
}

template<class TheClass>
void LinkedQueue<TheClass>::print(void) const {
    cout << "打印动态队列：[ ";
    lq_node<TheClass> *currentNode = this->front;
    while(nullptr != currentNode) {
        cout << currentNode->val << ' ';
        currentNode = currentNode->next;
    }
    cout << ']' << endl;
}

}

#endif